package de.haw.gka.a1;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Set;

import org.jgrapht.graph.AbstractGraph;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.WeightedPseudograph;


public class AlgoHierholzer extends AbstractSearchAlgo {
	
	private AbstractGraph<Knoten, DefaultWeightedEdge> graph= new WeightedPseudograph<Knoten, DefaultWeightedEdge>(DefaultWeightedEdge.class);
	private List<Knoten> knotenWeg = new ArrayList<Knoten>();
	private List<DefaultWeightedEdge> kantenWeg= new  ArrayList<DefaultWeightedEdge>();
	
	public AlgoHierholzer(AbstractGraph<Knoten, DefaultWeightedEdge> aGraph){
            //graphen kopieren
            for(Knoten k: aGraph.vertexSet()){
	    		this.graph.addVertex(k);
    		}
            for(DefaultWeightedEdge e:aGraph.edgeSet()){
                Knoten von = aGraph.getEdgeSource(e);
                Knoten zu = aGraph.getEdgeTarget(e);
                this.graph.addEdge(von, zu, e);
            }
            // erzeugt die loesung
            algo();

    }
	
	private void algo(){

        List<Knoten> zwischenList= new ArrayList<Knoten>(graph.vertexSet());
        //Radom ersten Knoten waehlen
		Random generator = new Random();
		int random = generator.nextInt(graph.vertexSet().size());
		Knoten erster=zwischenList.get(random);
				
		//ziwchenliste zum weiterengebrauch clearen
		zwischenList.clear();
		//ersten Cycle finden
		knotenWeg.addAll(getCiycle(erster));
		Knoten current= erster;
		//solange wie graph kanten hat 
		while(!graph.edgeSet().isEmpty()){
			
			//wenn Knotengrat größer 1 dann auswählen
			for(Knoten knoten: knotenWeg){
				if(knotenGrad(knoten)>=2){
					current=knoten;
					continue;
				}
			}
			//index für knoten holen
			int index = knotenWeg.indexOf(current);
			//neuen Cycle holen
			zwischenList.addAll(getCiycle(current));
			//ausganzknoten aus liste loeschen
			knotenWeg.remove(index);
			//neuen Cycle hinzuf�gen auf Position des Startknotens
			knotenWeg.addAll(index, zwischenList);
            //zwischenlist löschen
			zwischenList.clear();
			
		}
 	}
	
	
	private int knotenGrad(Knoten k){
        //holt alle kanten vom Knoten
		Set<DefaultWeightedEdge> zwischen = graph.edgesOf(k);
		return zwischen.size();
	}
	
	private List<Knoten> nachbarKnoten(Knoten knoten){
		List<Knoten> nachbarList= new ArrayList<Knoten>();
		//durchläuft alle kanten eines Knoten
		for(DefaultWeightedEdge edge : graph.edgesOf(knoten)){	
			Knoten neighbor = graph.getEdgeSource(edge);
            // abfrage um die richtige reihenfolge der Kante zu bekommen zb a,b und nicht b,a
			if(neighbor.equals(knoten)){
				neighbor=graph.getEdgeTarget(edge);
			}
	       	nachbarList.add(neighbor); 
		}
		return nachbarList;
	}
	
	private List<Knoten> getCiycle(Knoten knoten){
		List<Knoten> cycle = new ArrayList<Knoten>();
		
		int start=1;
		Knoten current=null;
        // startknoten hinzu fuegen
		cycle.add(knoten);
        //solange bis start 0 ist und aktueller knoten = start knoten
		while (start!=0 || !current.equals(knoten)){
			//um start auf 0 zu setzen und aktuellen knoten auf start knoten
			if(start==1){
				current=knoten;
				start=0;
			}
            //holt sich ersten nachbarn vom aktuellen knoten
			Knoten auswahl = nachbarKnoten(current).get(0);
            //um die richtige kante folge zu loeschen
			if(graph.containsEdge(current, auswahl)){
                // globale liste aller abgelaufenner kanten
				kantenWeg.add(graph.getEdge(current, auswahl));
                //loescht kante aus graph
				graph.removeEdge(current, auswahl);
			}
			else{
				kantenWeg.add(graph.getEdge(auswahl, current));
				graph.removeEdge(auswahl, current);
			}
            //aktueller knoten = nachbar
            current=auswahl;
            //kntoen wird zum kreis hinzugefügt
            cycle.add(current);
		}
		
		return cycle;
	}

	@Override
	public List getTheShortestWay() {		
        return  kantenWeg;
	}
	public List getWay(){
		return knotenWeg;
	}
	
}
